/**********************************************************
                     sparse.c
this is a sparse matrix
written by CAS
***********************************************************/
#include <stdio.h>
#include <malloc.h>
#include <semaphore.h>

#include "clam.h"

extern void CTG_resources();

int Zget_pool_node(int i1,int i2);
void Zscore_grand(int i, int exponent);
static ZINSTANCE *II = NULL;

extern int *startRow, *endRow;

int *node_num, *node_limit, node_pool_size;
int active_threads;
sem_t active_threads_mutex;
ZNODE  *Znew_node_shared(int,int,int);
ZNODE  *Znew_node_serial(int,int);

/***************************************************************/
static void all_ok(i1, i2)
int i1, i2;
{
    if (II == NULL) {
       fprintf(stderr,"No II\n");
       printf("No II\n");
       exit(0);
    }
    if (II->pool == NULL) {
       fprintf(stderr,"No active II\n");
       printf("No active II\n");
       exit(0);
    }
    if (i1<0 || i1 >= II->size)  {
       fprintf(stderr,"Ztravers i1 (%d) is greater than max size %d \n",i1,II->size);
       exit(0);
    }
    if (i2<0 || i2 >= II->size)  {
       fprintf(stderr,"Ztravers i2 (%d) is greater than max size (%d)\n",i2,II->size);
       exit(0);
    }
}

/**************************************************************
                   DEF: Zcreate_instance
**************************************************************/
int Zcreate_instance(name, I, size)
char *name;
ZINSTANCE *I;
int size;
{
int i;

    if (size == 0) {
       fprintf(stderr,"No size\n");
       return 0;
    }
    if (II!=NULL && II == I && strcmp(name, II->name)==0)
    {  printf("Sparse matrix already exists for %s\n",II->name);
       Zdestroy_instance(I);
    }
    if (I->max != 0) Zdestroy_instance(I);

    I->size = size;
    I->matrix = (ZMATRIX *) calloc(size, sizeof(ZMATRIX));
    NOMEM3(I->matrix, "ZMATRIX", 0);

    if(!SHARED_OPTION)
    {
        for (i=0; i< size; i++) {
           I->matrix[i].cin = -1;
           I->matrix[i].first = -1;
        }
        I->max = size * 12;
        I->pool = (ZNODE *) calloc(I->max, sizeof(ZNODE));
        NOMEM3(I->pool, "ZNODE", 0);
        I->num = 0;
        strcpy(I->name ,name);
        II = I;
        return 1;
    }
    else
    {
        for (i=0; i< size; i++) {
            I->matrix[i].cin = -1;
            I->matrix[i].first = -1;
            I->matrix[i].last = -1;
        }
        sem_init(&I->mutex,0,1);
        sem_init(&active_threads_mutex,0,1);
        active_threads = 0;

        I->max = size * 12;
        I->pool = (ZNODE *) calloc(I->max, sizeof(ZNODE));
        NOMEM3(I->pool, "ZNODE", 0);

        I->num = 0;
        strcpy(I->name ,name);
        II = I;
        return 1;
    }
fprintf(stderr,"ERROR: create instance failed\n");
return 0;
}

/**************************************************************
                   DEF: Zactiviate_instance
**************************************************************/
void Zactivate_instance(I)
ZINSTANCE *I;
{
    II = I;
}

/**************************************************************
                   DEF: Zdestroy_instance
**************************************************************/
void Zdestroy_instance(I)
ZINSTANCE *I;
{

  if(SHARED_OPTION)
  {
     sem_destroy(&I->mutex);
     sem_destroy(&active_threads_mutex);
  }
  if (I == NULL) return;
  if (II == I) II = NULL;
  if (I->matrix != NULL) free(I->matrix);
  if (I->pool != NULL) free(I->pool);
  I->matrix = NULL;
  I->pool = NULL;
  I->size = I->num = I->max = 0;
  I->name[0] = '\0';
}

/***************************************************************
         DEF: Znew_node_shared
***************************************************************/
ZNODE  *Znew_node_shared(i1, i2, procID)
  int i1,i2, procID;
{
  ZNODE  *node = NULL;
  int i, num, first;

  all_ok(i1, i2);

  sem_wait(&II->mutex);
  if (II->num == II->max )
  {
       II->max +=  II->max * 0.5 ;

      /* Spin lock in order to make sure there are no active threads */
      while(active_threads) {}

      II->pool = (ZNODE *) realloc(II->pool, (II->max * sizeof(ZNODE)));

      if (II->pool==NULL) {
          fprintf(stderr,"\n**Memory allocation error: Max %d (%d bytes)\n",
                II->max, II->max*sizeof(ZNODE));
          CTG_resources();
          exit(0);
      }
  }
  num = II->num;
  II->num++;
  sem_post(&II->mutex);

  sem_wait(&active_threads_mutex);
  active_threads++;
  sem_post(&active_threads_mutex);

  first = II->matrix[i1].first;

  if ((node = Zif_exist(i1, i2))) {
     if (Ztrace == 2) printf("already exist %d %d\n",i1, i2);
     return node;
  }

  if (first == -1)
  {  /* row is presently empty, fill first */
      II->matrix[i1].first = num;
      II->matrix[i1].last  = num;
      II->pool[num].next = -1;
  }
  else if (II->pool[first].i2 > i2)
  {  /* This node precedes the first node on the row, insert */
      II->pool[num].next = first;
      II->matrix[i1].first = num;
  }
  else if (II->pool[II->matrix[i1].last].i2 < i2 )
  {
     II->pool[II->matrix[i1].last].next = num;
     II->pool[num].next = -1;
     II->matrix[i1].last = num;
  }
  else
  {
      /* Find the place we will be inserting */
     for (first = i = II->matrix[i1].first;
          II->pool[i].i2 < i2 && II->pool[i].next != -1;
          first = i, i = II->pool[i].next);
     II->pool[num].next = II->pool[first].next;
     II->pool[first].next = num;
  }

  if (num >= II->max) fprintf(stderr,"Num %d max %d\n",num, II->max);
     
  node = &(II->pool[num]);
  node->i1 = i1;
  node->i2 = i2;
  node->exponent = 0;

  sem_wait(&active_threads_mutex);
  active_threads--;
  sem_post(&active_threads_mutex);

  return node;
}

/***************************************************************
         DEF: Znew_node_serial
***************************************************************/
ZNODE  *Znew_node_serial(i1, i2)
  int i1,i2;
{
ZNODE  *node;
int i,j,k, num, first;

   all_ok(i1, i2);

   if ((node = Zif_exist(i1, i2)))
   {
     if (Ztrace == 2) printf("already exist %d %d\n",i1, i2);
     return node;
   }

   first = II->matrix[i1].first;

   if (II->num == II->max)
   {
      j = MiN(i1,i2);
      num = II->size - j; /* number left to process */
      i = (II->max/j);  /* 2x avg overlap */
      k = num*i;

      II->max += k;
      II->pool = (ZNODE *) realloc(II->pool, (II->max * sizeof(ZNODE)));
      if (II->pool==NULL) {
        fprintf(stderr,"\n**Memory allocation error: Max %d (%d bytes)\n",
           II->max, II->max*sizeof(ZNODE));
        CTG_resources();
        exit(0);
      }
   }

   num = II->num;
   II->num++;

  /* Gaurav 12/20/03; 'last' added */

   if (first == -1)
   {  /* row is presently empty, fill first */
      II->matrix[i1].first = num;
      II->matrix[i1].last  = num;
      II->pool[num].next = -1;
   }
   else if (II->pool[first].i2 > i2)
   {  /* This node precedes the first node on the row, insert */
      II->pool[num].next = first;
      II->matrix[i1].first = num;
   }
   else if (II->pool[II->matrix[i1].last].i2 < i2 )
   {
      II->pool[II->matrix[i1].last].next = num;
      II->pool[num].next = -1;
      II->matrix[i1].last = num;
   }
   else
   {
      /* Find the place we will be inserting */
      for (first = i = II->matrix[i1].first;
         II->pool[i].i2 < i2 && II->pool[i].next != -1;
         first = i, i = II->pool[i].next);
      II->pool[num].next = II->pool[first].next;
      II->pool[first].next = num;
   }
   node = &(II->pool[num]);
   node->i1 = i1;
   node->i2 = i2;
   node->exponent = 0;

   return node;
}
/***************************************************************
         Zdelete_node
***************************************************************/
void Zdelete_node(i1, i2)
int i1, i2;
{
ZNODE *node;
  if ((node = Zif_exist(i1, i2)))
      node->exponent  = -1;
}

/***********************************************************************
       Ztraverse
************************************************************************/
static int old_i1= -1, next_i2= -1;

ZNODE *Ztraverse(i1)
int i1;
{
     all_ok(i1, 0);
     if (II->matrix[i1].first == -1) return NULL;

     if (old_i1 != i1 || next_i2 == -1)
        next_i2 = II->matrix[i1].first;
     else
        next_i2 = II->pool[next_i2].next;
     old_i1 = i1;
     if (next_i2 == -1) return NULL;
     return &(II->pool[next_i2]);
}

/*******************************************************************
         Zif_node
*********************************************************************/
int  Zif_node(i1)
int i1;
{
   if (i1  >= II->size || II->matrix[i1].first== -1) return 0;
   return 1;
}

/*******************************************************************
         Zif_exist
*********************************************************************/
ZNODE  *Zif_exist(i1, i2)
int i1, i2;
{
int i;

   all_ok(i1, i2);
   if (II->matrix[i1].first== -1) return NULL;

   for (i = II->matrix[i1].first;
      II->pool[i].i2 < i2 && II->pool[i].next != -1;
      i = II->pool[i].next);
      if (II->pool[i].i2 == i2)
           return &(II->pool[i]);
   return NULL;
}

/***********************************************************************
  the next few routines are for debugging
************************************************************************/
void Zdump_all()
{
int i;
ZNODE *node;
CLONE clone;

   printf("Sparse %s size %d num %d max %d\n",
            II->name, II->size, II->num, II->max);
   for (i=0; i< II->size; i++)
   {
      clone = arr(acedata, II->matrix[i].cin, CLONE);
      printf("\n%2d: %12s (cbmap %d grand %4d (%4d) high %4d mtype %d nband %d)\n",
              i,clone.clone,
              II->matrix[i].cbmap+1, II->matrix[i].grand, II->matrix[i].save_grand,
              II->matrix[i].high_match, II->matrix[i].mtype,clone.fp->b2);
      if (II->matrix[i].first != -1) 
         while ((node = Ztraverse(i))) Zdump_node("Z",node);
   }
}

void Zdump_node(msg, node, size)
char *msg;
ZNODE *node;
{
CLONE clone;
   clone = arr(acedata, II->matrix[node->i2].cin, CLONE);
   printf("%12s: %d nband %2d exp %2d  (cbmap %d pick %4d left %4d right %4d) \n", clone.clone,
          node->i2,  clone.fp->b2, node->exponent,
          II->matrix[node->i2].cbmap+1, II->matrix[node->i2].pick,
          II->matrix[node->i2].leftb, II->matrix[node->i2].rightb);
}

void Zdump_matrix(int i)
{
CLONE clone;
ZNODE *node;
   if (II->matrix[i].cin == -1) return;
   clone = arr(acedata, II->matrix[i].cin, CLONE);
   printf("\n%2d: %12s %2d: ",i, clone.clone, clone.fp->b2);
   printf(" %d mtype %d exponent %d (%d %4d %4d %4d)\n", ZZ.matrix[i].grand,
       ZZ.matrix[i].mtype, ZZ.matrix[i].high_match,
       II->matrix[i].cbmap+1, II->matrix[i].pick, II->matrix[i].leftb, II->matrix[i].rightb);
   if (II->matrix[i].first != -1)
       while ((node = Ztraverse(i))) Zdump_node("Z",node, clone.fp->b2);

}

void Zdump_clhigh()
{
int i;
   for (i=0; i<ZZ.size; i++)
        if (ZZ.matrix[i].cin == clhigh->next) {
            Zdump_matrix(i);
            return;
        }
}

void Zdump_pool(char *msg)
{
int i;
  for (i=0; i<II->num; i++)
   if (II->pool[i].i1 < 0 || II->pool[i].i2 < 0)
      printf("%d %s Pool %d %d %d\n", ZS, msg, i, II->pool[i].i1, II->pool[i].i2);
}


/*********************************************************************
                     Zserver_fill
this is called from shared/shared.c
**********************************************************************/

void Zserver_fill() {
  int i,first, cj, ci, num, exponent, match;
  ZNODE  *node;
  void Zscore_grand2();

      /* we know how many nodes we will need */
  if (II->num*2 >= II->max ) {
      II->max +=   ((II->num * 2) - II->max) + 1;
      II->pool = (ZNODE *) realloc(II->pool, (II->max * sizeof(ZNODE)));
      if (II->pool==NULL) {
          fprintf(stderr,"\n**Memory allocation error: Max %d (%d bytes)\n",
             II->max, II->max*sizeof(ZNODE));
          CTG_resources();
          exit(0);
      }
  }

  /* Starting from bottom of the matrix assures that we always add at the
     front of the matrix, since the rows are kept in sorted order
  */
  for(ci=ZZ.size-1; ci>=0; ci--)
  {
      if( II->matrix[ci].first == -1 ) continue;

      for ( first = i = II->matrix[ci].first; /* II->pool[i].next != -1 */;
          first = i = II->pool[i].next) {

          cj = II->pool[first].i2;
          exponent = II->pool[first].exponent;
          match = II->pool[first].match;
          num = Zget_pool_node(ci,cj);

          if(II->matrix[cj].first == -1) {
             II->matrix[cj].first = num;
             II->pool[num].next = -1;
          }
          else {
             II->pool[num].next = II->matrix[cj].first;
             II->matrix[cj].first = num;
          }
          node = &(II->pool[num]);
          node->i1 = cj;
          node->i2 = ci;
          node->exponent =exponent;
          node->match = match;

          Zscore_grand(cj,exponent);
          if (II->pool[i].next == -1) break;
      }
   }
   for (ci=0; ci<ZZ.size; ci++) Zscore_grand2(ci); /* cari 17feb05 */
}

/************************************************************************
                           Zget_pool_node()
***********************************************************************/
int Zget_pool_node(int i1,int i2) {
  int num;

  if (II->num == II->max ) { /* this should not happen */

printf("Increase on get pool %d\n",II->max);
    II->max +=   II->max * 0.1;

    II->pool = (ZNODE *) realloc(II->pool, (II->max * sizeof(ZNODE)));

    if (II->pool==NULL) {
        fprintf(stderr,"\n**Memory allocation error: Max %d (%d bytes)\n",
           II->max, II->max*sizeof(ZNODE));
        CTG_resources();
        exit(0);
    }
  }
  num = II->num;
  II->num++;

  return num;
}

